Part A


Answers are before question 21.


1.

A microkernel is

A)

a kernel containing many components that are optimized to reduce resident memory size.

B)

a kernel that is compressed before loading in order to reduce its resident memory size.

C)

a kernel that is compiled to produce the smallest size possible when stored to disk.

D)

a kernel that is stripped of all nonessential components.



2.

When a child process is created, which of the following is a possibility in terms of the execution or address space of the child process?

A)

The child process runs concurrently with the parent.

B)

The child process has a new program loaded into it.

C)

The child is a duplicate of the parent.

D)

All of the above



3.

A race condition

A)

results when several threads try to access the same data concurrently.

B)

results when several threads try to access and modify the same data concurrently.

C)

will result only if the outcome of execution does not depend on the order in which instructions are executed.

D)

None of the above



4.

Which of the following scheduling algorithms must be nonpreemptive?

A)

SJF

B)

Round-robin

C)

FCFS

D)

priority algorithms



5

The objective of multiprogramming is

A)

to have some process running at all times.

B)

to maximize the response time perceived by the user of the system.

C)

to allow multiple threads the ability to execute at the exact same time.

D)

to ensure that no thread must wait in the ready state.




6.

A cycle in a resource-allocation graph is

A)

a necessary and sufficient condition for deadlock in the case that each resource has more than one instance.

B)

a necessary and sufficient condition for a deadlock in the case that each resource has exactly one instance.

C)

a sufficient condition for a deadlock in the case that each resource has more than one instance.

D)

is neither necessary nor sufficient for indicating deadlock in the case that each resource has exactly one instance.



7.

The reader preferred readers-writers problem

A)

requires that, once a reader is ready, that reader performs its read as soon as possible.

B)

is not used to test synchronization primitives.

C)

requires that no reader will be kept waiting unless a writer has already obtained permission to use the shared database.

D)

requires that no reader will be kept waiting unless a reader has already obtained permission to use the shared database.



8.

Which of the following is used as a way to deal with deadlocks?

A)

ensure that a system will never enter a deadlocked state

B)

allow the system to enter a deadlocked state and then detect and recover

C)

ignore the deadlock altogether

D)

All of the above



9.

What is the average waiting time using the FCFS scheduling algorithm given that process one through three have burst times of ten, twenty, and thirty milliseconds respectively? Assume that the processes arrive in the order: one followed by two followed by three.

A)

10ms

B)

13.3ms

C)

20ms

D)

30ms



10.

An interrupt

A)

occurs when there are no processes left to execute.

B)

can be triggered by a system call.

C)

can, by definition, only occur through a hardware event.

D)

all of the above.





11.

Which of the following is a property of a hard real-time system?

A)

critical real-time tasks get priority over other tasks and retain that priority until execution time has been completed.

B)

lack deadline support

C)

easily support advanced operating system features

D)

guarantees that critical tasks are completed on time



12.

The following code, using Ruby locks, will result in what kind of problem


lock = Mutex.new

mutex.lock

criticalSection

mutex.lock

A)

no problem will result in most cases

B)

livelock

C)

mutual exclusion violation

D)

deadlock



13.

A dispatcher

A)

terminates a process.

B)

terminates a thread.

C)

gives control of the CPU to a process.

D)

is not required to be implemented at high speeds as it is invoked significantly less often than a context switch.



14.

An instruction that executes atomically

A)

must consist of only one machine instruction.

B)

executes as a single, uninterruptible unit.

C)

cannot be used to solve the critical section problem.

D)

All of the above



15.

Which of the following is not a property of a time sharing system?

A)

It is an extension of multiprogramming.

B)

It does not require an interactive computer system.

C)

It allows for multiple users to use the computer system.

D)

Each user is given the impression that the computer system is dedicated to his or her use.



16.

Multiprogramming has all of the following properties except:

A)

increases CPU utilization

B)

typically uses operating systems that are able to keep several jobs in memory

C)

is an important aspect in job scheduling

D)

often results in an idle CPU even though more jobs are available to execute



17.

If you were in charge of designing an operating system for a handheld computer, which of the following design considerations should you NOT consider to be a very important issue in such an application?

A)

power consumption

B)

user friendliness

C)

memory conservation

D)

support for cutting edge processor speeds



18.

Which of the following would be an unlikely design consideration for an operating system?

A)

efficiency

B)

user convenience

C)

real time performance

D)

None of the above




19.

What is the average waiting time using the SJF scheduling algorithm given that process one through three have burst times of twenty, ten, and thirty-five milliseconds respectively?

A)

10ms

B)

13.3ms

C)

20ms

D)

35ms



20.

A resident monitor was developed to

A)

keep track of operations in case they needed to be undone in the event of system malfunctions.

B)

manage memory in early computer systems.

C)

transfer control automatically from one job to the next.

D)

not exist in main memory.


Answer Key


1.D

2.D

3.B

4.C

5.A

6.B

7.C

8.D

9.B

10.B

11.D

12.D

13.C

14.B

15.B

16.D

17.D

18.D

19.B

20.C


Part B (2 marks each question)


21.

Give examples of where hard real-time and soft real-time systems are useful or required – one example each.


Hard real-time systems are used in devices where rigid time requirements are absolutely necessary. For example, systems that control simple scientific experiments, plane control systems, and medical imaging applications use this type of hardware.

Soft real-time systems are used when more advanced operating system features would be useful and when time restraints are looser. These types of systems are used in multimedia, virtual reality, and advanced scientific projects.

22.

Explain the concept of a context switch.



Switching from one process running to another. Whenever the CPU starts executing a new process, the old process's state must be preserved. The context of a process is represented by its process control block. This block of information must be exactly saved and the context of the new process loaded.



23.

Describe the difference between the fork() and clone() Linux system calls.



The fork call is actually a specialized version of the clone call. When a clone call is made a list of items to share between the clone (child) and its parent is passed. With a fork call the child effectively copies rather than shares the data of its parent. The clone() call is used to create threads that share all the parent address space.



24.

What is the difference between multilevel queue scheduling and multilevel feedback queue scheduling algorithms?



In both algorithms, processes are placed in queues. In a multilevel queue, processes are permanently assigned to a queue on entry into the system. The feedback queue, on the other hand, allows processes to move between queues.



25.

Explain how a race condition can happen.


A race condition can occur when several threads access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the accesses take place.

Part C (4 marks each question)


26.

Here are the arrival and burst times for a number of processes:


Process

Arrival Time

Burst Time

P1

0

4

P2

2

2

P3

3

5

P4

4

3

P5

7

1


From this table draw a Gantt chart showing a Shortest Job First schedule without preemption and calculate the average waiting time.

Not a Gantt chart but has the required information

P1:(0-4), P2:(4-6), P4(6-9), P5(9-10), P3(10-15)

Average wait time = (0 + 2 + 7 + 2 + 2) / 5 = 13/5 = 2.6


27.

Using the same table as in question 26, draw a Gantt chart showing a Shortest Job First schedule with preemption and calculate the average waiting time. If there are two or more processes with the same shortest remaining burst time and one is currently running, then do not preempt it.

Not a Gantt chart but has the required information

P1:(0-4), P2:(4-6), P4(6-7), P5(7-8), P4(8-10), P3(10-15)

Average wait time = (0 + 2 + 7 + (2+1) + 0) / 5 = 12/5 = 2.4


28.

Here is a Ruby version of a semaphore wait method.


  def wait
    Thread.critical = true
    if (@counter -= 1) < 0
      @waiting_list.push(Thread.current)
      Thread.stop
    end
  ensure
    Thread.critical = false
  end

Explain the importance of the Thread.critical lines.


It stops other threads being scheduled between the time the Thread.critical = true and either Thread.critical = false, or the running thread stops.

This is important because we don't want another thread accessing the semaphore data while the wait operation is running or we could get a race condition.


What does the value of the counter instance variable represent?


It is the semaphore value. In this case it holds the number of resources protected by this semaphore when the value is positive. When the value is negative it holds the negative of the number of threads waiting on this semaphore.


What does the waiting_list array contain?


The list of threads waiting on this semaphore.



29.

The following timing results were obtained from assignment 1.



Explain why thread creation is faster than process creation.


It does less work. Process creation requires the allocation of a PCB and copies information from the parent, in particular the page table. Data pages that are modified are also copied. Threads share the same page table and don't copy any memory.

In the case of Ruby, the threads are also user-level and so they don't use any system calls, so they have no system call overhead either.


The real times and total times are almost identical for the thread creation. Explain why the same is not true for the process creation.


The real time includes the time spent waiting, i.e. not running on the CPU. This includes waiting while other processes are running and possibly waiting for things like memory to be allocated.

Many people said that the total time does not include the time of any child processes, this is not strictly true. Any child processes that have finished and are waited for do have their total times added to the total time of the parent.



30.

Here is some output from the Linux “top” command, when running processSwitchingBenchmark.rb from assignment 1. The processes are ordered according to the amount of CPU time they are using. There are five Ruby processes each calculating pi to 1000 decimal places.


Tasks: 85 total, 7 running, 78 sleeping, 0 stopped, 0 zombie

Cpu(s): 95.4% us, 4.6% sy, 0.0% ni, 0.0% id, 0.0% wa, 0.0% hi, 0.0% si

Mem: 777180k total, 504124k used, 273056k free, 36684k buffers

Swap: 0k total, 0k used, 0k free, 289032k cached

PID PPID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND

2781 2770 robert 25 0 9544 8256 1964 R 20.5 1.1 0:00.70 ruby

2782 2770 robert 25 0 10720 9392 1964 R 19.8 1.2 0:00.60 ruby

2783 2770 robert 25 0 10720 9376 1964 R 19.2 1.2 0:00.58 ruby

2784 2770 robert 25 0 10720 9376 1964 R 17.5 1.2 0:00.53 ruby

2785 2770 robert 25 0 10192 8820 1964 R 17.2 1.1 0:00.52 ruby

2437 2426 root 15 0 91712 18m 80m S 3.6 2.4 0:15.74 X

2727 1 robert 15 0 27664 13m 20m S 0.7 1.7 0:01.94 gnome-terminal

2680 1 robert 16 0 19704 8148 16m S 0.3 1.0 0:00.67 clock-applet

2747 2729 robert 16 0 3160 912 1620 R 0.3 0.1 0:00.44 top

1 0 root 16 0 1984 464 1316 S 0.0 0.1 0:01.45 init

Each of the Ruby processes has the same parent process. Explain why the parent process 2770 is not visible in the output.


The parent process is waiting for its children. Hence it is not currently running. It will be in the table but somewhere way down the bottom.


Apart from the Ruby processes which other processes are runnable?


Even though the table says that 7 processes are running. The only runnable process (running or ready to run) you can see is “top” process 2747.


The five Ruby processes are all executing exactly the same code, explain why they have used different percentages of the available CPU time.


The scheduler does not guarantee to exactly fairly schedule processes. Depending on exactly when the top command took its measurement there could also be some influence on which processes started first. However it is not true that they have different priorities. All five processes have a priority of 25 with a nice value of 0.